De la Mihai Badoiu

Faptul ca din fiecare state ai doar 2 tranzitii nu te ajuta la nimic. Oricum
  problema de a minimiza un DFA este cunoscuta. Va voi da un algorithm si 
  voi ganditi-va cum sa demonstrati 3 lucruri: 1. DFA-ul produs este echivalent
  2. este minimal 3. algoritmul termina in time polinomial. (daca nu va
  prindeti poate va trimit eu demonstratiile intr-o saptamana or so, asta
  in caz ca va intereseaza)

  Notatii:
  Q => set finit de stari
  \sigma => {0,1}
  delta:Q x {0,1} -> Q  => functia de tranzitie
  q_0 \in Q => starea initiala

  Alg:
  1. pt fiecare stare finala, modifica tranzitiile de 0 si 1 catre el.
  2. scoate toate starile la care nu poti sa ajungi.
  3. construieshte urmatorul graf nedirectat G ale carui noduri sunt starile
  4. adauga muchii intre fiecare stare finala de fiecare state ne-finala
  5. repeta pana cand nu mai poti sa adaugi:
  6.   pt orice pareche de stari distincte q si r si fiecare a \in {0,1}
  7.      adauga muche (q,r) in G daca (delta(q,a), delta(r,a)) este
          muche in G. (delta este functia de tranzitie, delta(q,a) = nodul
          in care ajungi daca din starea q treci pe tranzitia a.
  8. pt fiecare stare q,
          lasa [q]={r \in Q cu proprietatea ca nici o muche nu uneshte q si
                    r in G, inclusiv r=q}
  9. Formeaza urmatorul DFA:
       Q' = {[q] | q \in Q} (daca [q]=[r], doar una dintre ele o sa fie in Q')
       delta'([q],a)=[delta(q,a)], pt orice q \in Q si a \in {0,1}
       q_0'=[q_0]
       A'={[q] | q \in A}

  --mihai

  >suntem la lotul national de info si azi am avut baraj. chestia 
  care ne-a lasat masca e urmatoarea: se da un au
  >tomat finit cu n noduri si din fiecare nod se poate trece in fix 
  alte doua (se citeste un sir de 0 si 1). exis
  >ta logic si stari finale la care se poate ajunge si inaintea terminarii 
  intrarii  (rezultat pozitiv). daca nu 
  >se ajunge la o stare finala inaintea de terminarea input-ului ai 
  rezultat negativ. prob: sa se rescrie automat
  >ul cu un numar minim de stari.
  >
  >cred ca problema nu e chiar grea, dar noi (lotul de info) nu stim 
  mai nimic teorie despre automate finite. cat
  >e ceva despre asta pe lista ar fi apreciat.
  >
  >mihai_p
  >
 